2018-2019 ICPC NEERC Southern Subregional Contest

7/13
总结:只会做水题


题目链接

A

  • 建图bfs,把 $\rm (sum, mod)$ 看成每个点的状态。
  • 可以发现的是长度可以很长,但对于同一个 $\rm sum$ 余数只有 $\rm [0,9]$ 这十种,故状态数最多 $d·s$ 种。

B

题意

题解


C

  • 显然是线段树的题,赛时想了没想出怎么保证复杂度。
  • 实际上,设置区间的 $\rm max,min,lazy$。
  • 一开始建树将所有点赋值为 $k$, 若一个区间 $max\geq $ 更新的数量,直接对这个区间进行 $\rm lazy$标记。反之,则递归更新直接更新到底,虽然这样看起来很费时,实际上更新到底的节点(天)以后都不用再更新了,因为需要的量已经够了。
  • 实际上就是一个线段树区间 $max, min, lazy$ 组合题。

D

模拟即可


E

  • 一个直观的感觉是, $d$ 太大会使得很多任务都要做,这样可能不是最优,因为耽误了可能 $d$ 更小的没做,不是最优解。$d$ 太小的话会使很多任务不能做,导致时间用不完,不是最优解。
  • 故可先二分一个最大 $d$ 使得完成所有能完成的任务在 $t$ 时间内,但这可能不是最优的,因为可能 $d$ 稍微大一点,虽然不能完成所有能完成的任务在 $d$ 时间内,但多完成了一些在 $d$ 较小的时候没有完成的,最优解只可能在这两者之间。
  • 故二分最大 $d$, 最优再判一下 $d+1$ 和 $d$ 谁最优。

F

贪心即可


G

题意

题解


H

模拟即可


I

题意

题解


J

题意

题解


K

模拟即可


L

题意

题解


M

题意

题解